동적 프로그래밍

미국의 응용수학자 리처드 E. 벨만이 제시한 최적화 이론의 한 갈래. 현대에는 그 의미가 확장되어 문제 풀이 기법 혹은 최적화 기법으로 인식된다.

기본적으로 동적 프로그래밍은 최적 제어 문제를 해결하기 위해서 고안된 방법이다. 특히나 이산 시간(discrete time) 제어 문제에 적용하기 위한 방법으로 시작한다. 최적제어는 어떤 시스템의 상태 $x(t)$와 현재의 입력 $u(t)$을 기반으로 계산되는 비용 $J(t)$을 최소화 하는 문제상황을 말한다. 벨만은 이 문제를 해결하기 위해서 핵심 개념을 제시하는데 이것이 바로 최적성의 원리이다. 최적성의 원리란 별로 어렵지 않다. 어떤 문제에 대한 최적의 경로(=비용을 최소화 하는)가 존재할때, 그 하위 경로 역시 최적이어야 한다라는 의미이다. 때문에 동적 프로그래밍은 문제를 전체적으로 한 번에 푸는 것이 아니라, 문제를 시간적으로 나누어 각 시점마다 최적의 결정을 순차적으로 내려가는 방식으로 접근한다.

상태기반의 문제를 재귀적으로 해석하는 방법은 너무나도 일반화 하기 쉬운 강력한 방법이었다. 이 문제를 최적제어 문제에만 쓰기 아까웠던 사람들은 다른 문제에도 사용하기 시작하였고 최적 경로, 그래프 탐색 문제등을 시작으로 동적 프로그래밍의 사상 아래에서 해결될 수 있음을 보였다.

이와 관련된 대표적인 예제는 동적 프로그래밍의 방법을 적용하여 피보나치 수열을 최적화 하는 문제가 있다. 아래의 코드는 Dictionary<int, int[]> 형태의 자료구조에 계산 값을 저장한 뒤, 중복된 계산식이 호출되면 해당 자료구조에서 이전에 계산된 값을 확인 후, 계산 값을 반환하여 불필요한 계산삽질을 처리하지 않게 한다.

Dictionary<int, int[]> dicFibo = new Dictionary<int, int[]>();

public int[] Getfibonacci(int n)
{
    if (n == 0)
    {
        if (!dicFibo.ContainsKey(0))
            dicFibo.Add(0, new int[] { 1, 0 });

        return new int[] { 1, 0 };
    }
    else if (n == 1)
    {
        if (!dicFibo.ContainsKey(1))
            dicFibo.Add(1, new int[] { 0, 1 });

        return new int[] { 0, 1 };
    }
    else
    {
        if (dicFibo.ContainsKey(n))
        {
            return dicFibo[n];
        }
        else
        {
            dicFibo[n] = new int[] { Getfibonacci(n - 1)[0] + Getfibonacci(n - 2)[0] , Getfibonacci(n - 1)[1] + Getfibonacci(n - 2)[1] };
            return dicFibo[n];
        }
    }
}

그의 자서전에 따르면 공군놈들이 연구 이름을 '의사 결정 프로세스'라고 재미없게 지으니까 좆같이 굴길래 '다이나믹 프로그래밍' 이라는 간지나는 이름을 붙였더니 좋아했다고 한다.[1]

보통은 코딩 새싹반 C나 C++을 배울때 피보나치 수열을 최적화하면서 처음 접하게 된다.

재귀함수나 반복문으로 구현한다. 재귀로 구현할 때 depth가 너무 깊어지면 저지 사이트에서 돌리다가 메모리 초과! 가 뜰 수도 있으니 주의하자. 짱구를 잘만 굴리면 flatten할 수 있는 케이스가 많이 있다.